package com.algorithm.sort;

/**
 * @program: 堆排序
 * @author: luhd
 * @create: 2021-08-12
 */
public class HeapSort {
    public static void main(String[] args) {
        /**
         * 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算。
         * 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
         * 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
         * 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
         * 简要描述：就是将最大的元素调至堆顶，然后与最后一个元素交换，最后一个元素就是最大的，同理，继续找出剩余元素最大的放到堆顶，与倒数第二个元素交换。。。。。
         */
        int [] arr = {15,5,3,7,9 ,2,18,10,20,6};
        HeapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    static int len;  // 声明全局变量,用于记录数组的长度，即无序区的长度

    /**
     *  堆排序算法
     *  构建一个大堆，将堆顶元素与末位元素交换位置，然后再重新调整最大堆
     * @param arr
     * @return
     */
    public static int[] HeapSort(int[] arr){
        len = arr.length;
        if(len < 1) return arr;
        //构建一个大堆
        buildMaxHeap(arr);
        while(len > 0){ //循环条件，无序区的大小大于0时
            swap(arr, 0, len-1);  //len-1为数组末位下标，与堆顶元素交换，即数组下标为0的值
            len--;  //交换过后，无序区的长度-1
            adjustHeap(arr,0);  //因为堆顶元素被替换，影响了最大堆的结构所以需要重新调整
        }
        return arr;
    }

    /**
     *  建立最大堆
     * @param arr 数组
     */
    public static void buildMaxHeap(int[] arr){
        for (int i = (len/2 - 1); i >= 0 ; i--) {   // (len/2 - 1)为堆的最后一个非叶子节点 的 数组下标
            // 从最后一个根节点往第一个根节点遍历，使之成为最大堆，即根节点都是最大值
            adjustHeap(arr,i);
        }
    }

    /**
     *  调整使之成为一个大堆
     * @param arr 数组
     * @param i 数组下标(根节点，非叶子节点，和叶子节点比较值的大小)
     */
    public static void adjustHeap(int[] arr, int i){
        int maxIndex = i; // 声明最大值的数组下标
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if(i*2 < len && arr[maxIndex] < arr[2*i])
            maxIndex = 2*i;
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if(i*2 +1 < len && arr[maxIndex] < arr[2*i +1])
            maxIndex = 2*i +1;
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整 与 父节点交换的位置(将最大值 赋给 父节点，父节点的值给了自己，有可能导致叶子节点比现在的值大，所以需要调整)
        if(maxIndex != i){
            swap(arr,i,maxIndex);
            adjustHeap(arr,maxIndex);
        }

    }
    //交换数组元素
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
